package org.xqh.study.leetcode.algorithm.linkedlist;

import org.xqh.study.leetcode.algorithm.linkedlist.RemoveNthFromEnd.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @ClassName MergeLinkList
 * @Description 合并K个升序链表
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * @Author xuqianghui
 * @Date 2021/2/5 16:34
 * @Version 1.0
 */
public class MergeLinkList {

    public static void main(String[] args) {
        ListNode[] lists = new ListNode[5];
//        lists[0] = new ListNode(-2, new ListNode(-1, new ListNode(-1, new ListNode(-1))));
//        lists[1] = null;
        for(int i = 0; i < 5; i++){
            lists[i] = new ListNode(i, new ListNode(i + 1, new ListNode(i + 2)));
        }
        ListNode merge = mergeKLists(lists);
        System.out.println("");
    }


    /**
     * 分治合并方法 对有序链表两两合并
     * 例如 k个 有序链表 k --> k/2 --> k/4 --> k/8
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0){
            return null;
        }

        while (lists.length > 1){
            lists = merge(lists);
        }

        return lists[0];
    }

    public static ListNode[] merge(ListNode[] lists){
        int len = lists.length;
        int mid = (len + 1) / 2;
        ListNode[] nlist = new ListNode[mid];
        for (int i = 0; i < mid; i++) {
            ListNode mn = lists[i];
            ListNode mn2 = null;
            int other = len - i - 1;
            if(i != other){
                mn2 = lists[other];
            }
            nlist[i] = MergeLinkListUtils.mergeTwo(mn, mn2);
        }
        return nlist;
    }

    /**
     * 合并多个 有序链表  优先队列 实现
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists2(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode node1, ListNode node2) {
                return node1.val - node2.val;
            }
        });
        for (ListNode node : lists) {
            if (node != null) {
                queue.offer(node);
                ListNode tmp = node.next;
                while (tmp != null) {
                    queue.add(tmp);
                    tmp = tmp.next;
                }
            }
        }

        ListNode result = queue.poll();
        ListNode tmp = result;
        while (!queue.isEmpty()) {
            ListNode next = queue.poll();
            tmp.next = next;
            tmp = tmp.next;
        }
        if (null != tmp) {
            tmp.next = null;
        }
        return result;
    }
}
